% $Header: /cvsroot/latex-beamer/latex-beamer/solutions/conference-talks/conference-ornate-20min.en.tex,v 1.7 2007/01/28 20:48:23 tantau Exp $

\documentclass{beamer}

\mode<presentation>
{
  %\usetheme{Warsaw}
  \usetheme{Antibes}
  \setbeamercovered{transparent}
  % or whatever (possibly just delete it)
}

\usepackage[english]{babel}
\usepackage[latin1]{inputenc}
\usepackage{times}
\usepackage[T1]{fontenc}
\usepackage{tikz}
\usepackage{amssymb, amsmath}

\setbeamertemplate{footline}[frame number]    % add slide number

%\usepackage{pdflibraryarrows}
% Or whatever. Note that the encoding and the font should match. If T1
% does not look nice, try deleting the line with the fontenc.

\title[Enabling and Controlling Diffusion Processes in Networks] % (optional, use only with long paper titles)
{Enabling and Controlling Diffusion Processes in Networks}

%\subtitle
%{Ph.D. Thesis Proposal}

\author[] % (optional, use only with lots of authors)
{Zhifeng~Sun}
% - Give the names in the same order as the appear in the paper.
% - Use the \inst{?} command only if the authors have different
%   affiliation.

\institute[Northeastern University] % (optional, but mostly needed)
{
  %\inst{1}%
  Department of Computer Science\\
  Northeastern University
}

\date[April 13, 2012] % (optional, should be abbreviation of conference name)
{April 13, 2012}
% - Either use conference name or its abbreviation.
% - Not really informative to the audience, more for people (including
%   yourself) who are reading the slides online

\subject{Theoretical Computer Science}
% This is only inserted into the PDF information catalog. Can be left
% out. 

% Delete this, if you do not want the table of contents to pop up at
% the beginning of each subsection:
\AtBeginSubsection[]
{
  \begin{frame}<beamer>{Outline}
    \tableofcontents[currentsection,currentsubsection]
  \end{frame}
}


% If you wish to uncover everything in a step-wise fashion, uncomment
% the following command: 

%\beamerdefaultoverlayspecification{<+->}

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%
% macros
\newcommand{\junk}[1]{}


\begin{frame}
  \titlepage
\end{frame}

\junk{
\begin{frame}{Outline}
  \tableofcontents
  % You might wish to add the option [pausesections]
\end{frame}
}

\section{Introduction}

\begin{frame}{Diffusion process}
\begin{itemize}
\item Diffusion is the spread of information or commodities in the
  network through local transmissions.
\item Harmful/Negative diffusions:
  \begin{itemize}
  \item Diffuse harmful information (e.g. diseases, viruses).
  \item Analyze the converging time and the extend of diffusion
    processes
  \item Design good intervention strategies.
  \end{itemize}
\item Positive diffusions:
  \begin{itemize}
  \item Diffuse useful information (e.g. innovations, ideas).
  \item Analyze the converging time of diffusion processes.
  \item Design efficient algorithms for fast diffusion.
  \end{itemize}
\end{itemize}
\end{frame}

\begin{frame}{Motivation}
\begin{columns}
  \column{0.5\textwidth}
  %\begin{exampleblock}{Human contact network}
    \begin{figure}
      \includegraphics[width=\textwidth]{fig/human.jpg}
    \end{figure}
  %\end{exampleblock}
 \begin{itemize}
    \item Innovations, ideas, gossip.
   \item Diseases.
    \item Friendship.
  \end{itemize}

  \column{0.5\textwidth}
  %\begin{exampleblock}{Computer network}
    \begin{figure}
      \includegraphics[width=.9\textwidth]{fig/netwk.jpg}
    \end{figure}
  %\end{exampleblock}
  \begin{itemize}
    \item Resource discovery.
    \item Computer viruses.
    \item Also sensor networks, mobile networks, etc.
  \end{itemize}
\end{columns}
\end{frame}

\begin{frame}{Thesis concentration}
\begin{itemize}
\item What is the optimal intervention strategy for a given contact
  network?
\item How effective are interventions of individual choices and
  behaviors.
  \begin{itemize}
  \item Individuals make their own intervention strategies.
  \item Individuals exhibit risk behavior changes.
  \end{itemize}
\item Analyze positive diffusions on dynamic networks.
  \begin{itemize}
  \item Resource discovery in the networks of gossip.
  \item Information dissemination in adversarial networks.
  \end{itemize}
\end{itemize}
\end{frame}

\begin{frame}{Outline}
  \tableofcontents
  % You might wish to add the option [pausesections]
\end{frame}

\section{Controlling harmful diffusions}

\subsection{Models for harmful diffusions}

\begin{frame}{Model}
\begin{itemize}
\item Contact graph: $G=(V,E)$.
\item Intervention: $a_i \in \{0,1\}$
  \begin{itemize}
  \item $a_i = 1$: node $i$ takes intervention.
  \item $a_i = 0$: node $i$ dosen't take intervention.
  \end{itemize}
\item Intervention vector: $\bar a = (a_1, a_2, \dots, a_n)$.
\item Intervention cost and infection cost: $C_i, L_i$.
\item Individual cost: $\cost{\bar a}=a_i C_i + (1-a_i) p_i(\bar a)
  L_i$, where $p_i(\bar a)$ is the probability that node $i$ gets
  infected given $\bar a$.
\item Social cost: $\sum_i \cost{\bar a}$.
\item We assume the infection is initialized at a node randomly picked
  according to an arbitrary probability distribution $\bar w = (w_1,
  w_2,\dots, w_n)$.
\item Disease transmission locality parameter $d$: how far the disease
  can transmit from the source node.
\end{itemize}
\end{frame}

\junk{
\begin{frame}{Disease model}
\begin{itemize}
\item We assume the infection is initialized at a node randomly picked
  according to an arbitrary probability distribution $\bar w = (w_1,
  w_2,\dots, w_n)$.
\item Disease transmission:
  \begin{itemize}
  \item Transmit at most $d$ hops in the contact graph.
  \item For each edge $(u,v)$, $p(u,v)$ is the probability that
    disease transmits from $u$ to $v$.
  \end{itemize}
\end{itemize}
\end{frame}
}
\begin{frame}{Example ($d=2$)}
\begin{columns}
  \column{0.5\textwidth}
  \begin{exampleblock}{Original graph}
  \begin{figure}
    \includegraphics[width=\textwidth]{fig/modelex.jpg}
  \end{figure}
  \end{exampleblock}

  \column{0.5\textwidth}
  \begin{exampleblock}{A and F take interventions}
  \begin{figure}
    \includegraphics[width=\textwidth]{fig/modelex0.jpg}
  \end{figure}
  \end{exampleblock}
\end{columns}
\end{frame}

\begin{frame}{Example ($d=2$)}
\begin{columns}
 \column{0.5\textwidth}
 \begin{exampleblock}{B started infection}
  \begin{figure}
    \includegraphics[width=\textwidth]{fig/modelex1.jpg}
  \end{figure}
  \end{exampleblock}

  \column{0.5\textwidth}
  \begin{exampleblock}{Spread distance $d$}
  \begin{figure}
    \includegraphics[width=\textwidth]{fig/modelex2.jpg}
  \end{figure}
  \end{exampleblock}
\end{columns}
\end{frame}

\subsection{Centralized intervention strategies}

\begin{frame}{Centralized strategies}
Problem definition:
\begin{itemize}
\item Given any contact graph, find intervention vector $\bar a$ to
  minimize the social cost $\sum_i \cost{\bar a} = \sum_i \left[ a_i
    C_i + (1-a_i) p_i(\bar a) L_i\right]$.
\end{itemize}

Our results:
\begin{itemize}
\item Computing the social optimum is NP-complete for all $d$.
\item Give an LP based approximation algorithm.
  \begin{itemize}
  \item $d<\infty$: $2d$-approximation.
  \item $d=\infty$: $O(\log n)$-approximation.
  \end{itemize}
\item Results published in [Kumar-Rajaraman-Sun-Sundaram 2010].
\end{itemize}
\end{frame}

\begin{frame}{Related work}
\begin{itemize}
\item \mbox{} [Aspnes-Chang-Yampolsky 2006] introduced a basic model for
  $d=\infty$ case with uniform intervention and infection costs which
  we have generalized here.
  \begin{itemize}
  \item Give an $O(\log^{1.5} n)$-approximation for social optimum.
  \end{itemize}
\item \mbox{} [Chen-David-Kempe 2010] independently gave an $O(\log
  n)$-approximation algorithm.
\item \mbox{} [Dezs\"{o}-Barab\'{a}si 2002] studied how to control
  virus transmission on scale-free networks.
\item \mbox{} [Borgs-Chayes-Ganesh 2010] studied how to distribute antidotes
  to control epidemics.
\item Considerable work in SIR and SIS models in epidemiology.
\end{itemize}
\end{frame}

\begin{frame}{Example for calculating $p_i(\bar a)$}
\begin{columns}
  \column{0.5\textwidth}
 \begin{figure}
    \includegraphics[width=\textwidth]{fig/modelex0.jpg}
  \end{figure}

  \column{0.5\textwidth}
  \begin{itemize}
  \item Initial infection probability is $1/8$ for all nodes.
  \item $d=2$: $p_B(\bar a) = 5/8$, and $p_G(\bar a) = 3/8$.
  \item $d=\infty$: $p_B(\bar a) = p_G(\bar a) = 6/8$.
  \end{itemize}
\end{columns}
\end{frame}

\begin{frame}{Approximation algorithm for social optimum}
\begin{block}{LP formulation}
\begin{itemize}
  \item Let $P^d_{ij}$ denote the set of all simple paths from $i$ to $j$ of length at most $d$.
  \item $\forall v\in V$, $x_v = 1$ if $v$ is secure; $x_v = 0$ otherwise.
  \item $\forall i,j\in V$, $y_{ij} = 1$ is there is no $p \in P^d_{ij}$ consisting entirely of insecure nodes.
\end{itemize}
\begin{eqnarray*}
\min & \sum_{v} C_v\cdot x_v + \sum_{j\in V} L_j \sum_{i \in V} w_i(1-y_{ij})  \nonumber \\
\mbox{s.t.} & \sum_{v\in p} x_v\ge y_{ij} \,\,\, \forall p\in P^d_{ij}   \\
& x_v \in \{0,1\}  \,\,\forall v\in V \nonumber\\
& y_{ij} \in \{0,1\}  \,\, \forall i,j\in V \nonumber
\end{eqnarray*}
\end{block}
\end{frame}

\begin{frame}{LP in details}
\vspace{-.2in}
\begin{eqnarray*}
\min & \sum_{v} C_v\cdot x_v + \sum_{j\in V} L_j \sum_{i \in V} w_i(1-y_{ij})  \nonumber \\
\mbox{s.t.} & \sum_{v\in p} x_v\ge y_{ij} \,\,\, \forall p\in P^d_{ij} 
\end{eqnarray*}
\vspace{-.2in}
\begin{itemize}
\item First part of the objective function corresponds to the cost of
  securing nodes.
\item Second part corresponds to the infection cost. For node $j$, its
  infection cost is $L_j$ times the sum of the probabilities of all
  nodes that have a path to $j$ of length at most $d$ consisting
  entirely of insecure nodes.
\item Constraint says, in order to separate a pair of nodes $i$ and
  $j$, we need to secure at least one node in every path between these
  two.
\end{itemize}
\end{frame}

\junk{
\begin{frame}{Constraints of LP}
\vspace{-.2in}
\begin{eqnarray*}
\min & \sum_{v} C_v\cdot x_v + \sum_{j\in V} L_j \sum_{i \in V} w_i(1-y_{ij})  \nonumber \\
\mbox{s.t.} & \sum_{v\in p} x_v\ge y_{ij} \,\,\, \forall p\in P^d_{ij} \\
& x_v \in \{0,1\}  \,\,\forall v\in V \nonumber\\
& y_{ij} \in \{0,1\}  \,\, \forall i,j\in V \nonumber
\end{eqnarray*}
\begin{itemize}
\item Constraint says, in order to separate a pair of nodes $i$ and
  $j$, we need to secure at least one node in every path between these
  two.
\end{itemize}
\end{frame}
}

\begin{frame}{Example of LP constraints}
\begin{columns}
  \column{0.5\textwidth}
  \begin{figure}
    \includegraphics[width=\textwidth]{fig/modelex.jpg}
  \end{figure}

  \column{0.5\textwidth}
  \begin{itemize}
  \item $d=2$.
  \item Look at the constraints for A, D pair.
    \begin{itemize}
    \item $x_A+x_B+x_D \ge y_{AD}$
    \item $x_A+x_C+x_D \ge y_{AD}$
    \end{itemize}
  \end{itemize}
\end{columns}
\end{frame}

\begin{frame}{Algorithm overview}
\begin{itemize}
\item Solve the LP, and obtain fractional solutions $(x,y)$.
  \begin{itemize}
  \item $d$ is a constant:
    \begin{itemize}
    \item Number of paths of length at most $d$ is polynomial.
   \end{itemize}
  \item $d$ is not a constant:
    \begin{itemize}
    \item Number of paths superpolynomial; still LP solvable using ellipsoid method.
   \end{itemize}
  \end{itemize}
\item Partial rounding to obtain integral $y$ values.
\item Final rounding to obtain integral $x$ values.
\item Show the cost of integral solution is within $2d$ or $O(\log n)$
  factor of the optimal LP solution.
\end{itemize}
\end{frame}

\junk{
\begin{frame}{Solving LP}
\begin{itemize}
\item $d$ is a constant:
  \begin{itemize}
    \item Number of paths of length at most $d$ is polynomial.
    \item So LP is poly-size and can be solved in poly-time.
  \end{itemize}
\item $d$ is not a constant:
  \begin{itemize}
    \item Number of paths superpolynomial; still LP solvable using ellipsoid method.
    \item Can also solve an equivalent LP of polynomial size.
  \end{itemize}
\end{itemize}
\end{frame}
}

\begin{frame}{Partial rounding}
\begin{eqnarray*}
\min & \sum_{v} C_v\cdot x_v + \sum_{j\in V} L_j \sum_{i \in V} w_i(1-y_{ij})  \nonumber \\
\mbox{s.t.} & \sum_{v\in p} x_v\ge y_{ij} \,\,\, \forall p\in P^d_{ij}
\end{eqnarray*}
\begin{itemize}
\vspace{-15pt}
\item Let $(x, y)$ denote an optimal solution.
\item Round each $y_{ij}$ to nearest integer.
  \begin{itemize}
    \item So values at least 1/2 are rounded up to 1 and less than 1/2 rounded down to 0.
  \end{itemize}
\item Scale up each $x_{v}$ by a factor of 2.
  \begin{itemize}
    \item If scaled value exceeds 1, set it to 1.
  \end{itemize}
\item New solution $(x,y)$ is still feasible and new cost at most twice that before.
\end{itemize}
\end{frame}

\begin{frame}{Final rounding}
\[\sum_{v\in p} x_v\ge y_{ij} \,\, p\in P^d_{ij} \]
\begin{itemize}
\item It remains to round the $x$-values.
\item Simple approach: Each $x_{v}$ that is at least $1/d$ is rounded up to 1, other $x_{v}$s rounded down to 0.
  \begin{itemize}
    \item Yields $2d$-approximation.
    \item Perhaps acceptable for small $d$.
  \end{itemize}
\item For $d=\infty$:
  \begin{itemize}
  \item Need to select a set of nodes to secure such that all pairs of nodes $i,j$ with $y_{ij} = 1$ are separated.
  \item This is precisely a vertex multicut problem for which $x$-values give a fractional optimum.
  \item Use algorithm of Garg-Vazirani-Yannakakis to round the $x$-values and obtain an $O(\log n)$-approximation.
  \end{itemize}
\end{itemize}
\end{frame}

\junk{
\begin{frame}{Final rounding}
\begin{eqnarray*}
\min & \sum_{v} C_v\cdot x_v + \sum_{j\in V} L_j \sum_{i \in V} w_i(1-y_{ij})  \nonumber \\
\mbox{s.t.} & \sum_{v\in p} x_v\ge y_{ij} \,\, p\in P^d_{ij}
\end{eqnarray*}
\vspace{-10pt}
\begin{itemize}
\item For $d=\infty$:
  \begin{itemize}
  \item Need to select a set of nodes to secure such that all pairs of nodes $i,j$ with $y_{ij} = 1$ are separated.
  \item This is precisely a vertex multicut problem for which $x$-values give a fractional optimum.
  \item Use algorithm of Garg-Vazirani-Yannakakis to round the $x$-values and obtain an $O(\log n)$-approximation.
  \end{itemize}
\end{itemize}
\end{frame}
}

\subsection{Decentralized intervention strategies}

\begin{frame}
Models:
\begin{itemize}
\item We use game theoretic analysis.
\item Strategy for each node is either taking the intervention ($a_i =
  1$) or not ($a_i = 0$).
\item Utility for each node is the cost function $\cost{\bar a}=a_i
  C_i + (1-a_i) p_i(\bar a) L_i$
\end{itemize}

\vspace{5pt}
Our results (published in [Kumar et al 2010]):
\begin{tabular}{|c|c|c|c|}
  \hline
  & $d=1$ & $1<d<\infty$ & $d=\infty$ \\
  \hline
  existence of pure NE & Yes & No/NP-complete & Yes \\
  \hline
  price of anarchy & $\Delta+1$ & & $O(1/\alpha(G))$ \\
  \hline
\end{tabular}
\begin{itemize}
\item $\Delta$ is the max degree in the contact graph.
\item $\alpha(G)$ is the vertex expansion of the contact graph.
\end{itemize}
\end{frame}

\begin{frame}{Related work}
\begin{itemize}
\item \mbox{} [Aspnes et al 2006] introduced a basic model for $d =
  \infty$ case that we have generalized here.
  \begin{itemize}
  \item Show existence of pure NE in a uniform version.
  \end{itemize}
\item \mbox{} [Kearns-Ortiz 2004] introduced interdependent security
  games.
  \begin{itemize}
  \item Similar to our model for special case of $d = 1$.
  %\item Crucial difference in assumption about initial infection.
  \end{itemize}
\item \mbox{} [Bauch-Earn 2004] used game theory to analyze
  vaccination uptake level to eradicate diseases.
\item \mbox{} [Omic et al 2009] introduced $n$-intertwined games.
  \begin{itemize}
  \item Based on SIS model for worm spread.
  \end{itemize}
\item \mbox{[Grossklags-Christin-Chuang 2008]} introduced information
  security games.
\end{itemize}
\end{frame}

\begin{frame}{Existence of pure NE when $d=\infty$}
\begin{theorem}
There is a pure NE when $d=\infty$.
\end{theorem}
\begin{itemize}
\item The existence proof is a potential function argument.
\item Define Threshold of a node, $t_i$: Bound on number of reachable
  nodes that would make the node want to secure itself.
  \[C_i \mbox{  vs  } L_i (t_i + 1)/n \,\, \Longrightarrow \,\, t_i = nC_i/L_i - 1\]
\item w.l.o.g., assume $t_1\ge t_2\ge \dots\ge t_m$.
\end{itemize}
\end{frame}

\begin{frame}{Potential function}
\begin{itemize}
\item Define potential function: $\hat{\Phi}(\vec{a}) =
  \left(\Phi_{1}(\vec{a}),\Phi_{2}(\vec{a}),\dots,\Phi_{n}(\vec{a})\right)$
  where $\Phi_{i}(\vec{a})$ is $0$ if $i$ is secure, $-1$ if $i$ is
  insecure and happy, and $1$ otherwise.
\end{itemize}
  \begin{columns}
    \column{0.5\textwidth}
   \begin{figure}
      \includegraphics[width=\textwidth]{./fig/func.jpg}
    \end{figure}
   
    \column{0.5\textwidth}
    \begin{itemize}
    \item $t_1=7,t_2=7,t_3=6,t_4=2,t_5=1,t_6=1$.
   \item 3 is secured.
    \item Potential function for this configuration is $\left( -1,-1,0,-1,1,1 \right)$.
    \end{itemize}
  \end{columns}
\end{frame}

\begin{frame}{Proof overview}
\begin{itemize}
\item Start with an arbitrary strategy vector $\bar a$.
\item Show potential function $\hat{\Phi}(\vec{a})$ decreases
  lexicographically when everyone does best response.
\item There is a lower bound on the potential function, thus will
  reach a stable value.
\item Everyone is satisfied with current strategy (pure NE).
\end{itemize}
\end{frame}

\begin{frame}{$\hat{\Phi}(\vec{a})$ lexicographically decreases}
\begin{itemize}
\item Case 1: unhappy insecure $\rightarrow$ happy secure. One
  component decreases by 1, while none of the other components
  increases.
\end{itemize}
\begin{figure}
  \includegraphics[width=\textwidth]{fig/func_case1.jpg}
\end{figure}
\end{frame}

\begin{frame}{$\hat{\Phi}(\vec{a})$ lexicographically decreases}
\begin{itemize}
\item $\hat{\Phi}(\vec{a}): \, \left( -1,-1,0,-1,1,1 \right)
  \rightarrow \left(-1,-1,0,-1,-1,0 \right)$
\end{itemize}
\begin{figure}
  \includegraphics[width=\textwidth]{fig/func_case1.jpg}
\end{figure}
\end{frame}

\begin{frame}{$\hat{\Phi}(\vec{a})$ lexicographically decreases}
\begin{itemize}
\item Case 2: unhappy secure $\rightarrow$ happy insecure. All the
  happy insecure nodes with bigger thresholds are still happy. Happy
  insecure nodes with smaller thresholds may become unhappy. But the
  function still decreases lexicographically.
\end{itemize}
\begin{figure}
  \includegraphics[width=\textwidth]{fig/func_case2.jpg}
\end{figure}
\end{frame}

\begin{frame}{$\hat{\Phi}(\vec{a})$ lexicographically decreases}
\begin{itemize}
\item  $\hat{\Phi}(\vec{a}): \, \left(-1,-1,0,-1,-1,0 \right)
  \rightarrow \left(-1,-1,-1,1,1,0\right)$
\end{itemize}
\begin{figure}
  \includegraphics[width=\textwidth]{fig/func_case2.jpg}
\end{figure}
\end{frame}

\junk{
\begin{frame}{Probabilistic transmission model}
\begin{itemize}
\item Calculation of the cost for an individual node is \#P-hard.
\item Pure NE may not exist.
\end{itemize}
\end{frame}
}

\section{Proposed research}

\subsection{Intervention strategies with the existence of risk behaviors}

\begin{frame}
Motivation:
\begin{itemize}
\item Drive faster with seat belt on.
\item Have more contact when vaccinated.
\item Take more risk with government bailout. 
\item How risk behavior is going to affect intervention strategies?
\end{itemize}

Model:
\begin{itemize}
\item Contact graph $G=(V,E)$.
\item Each node either applies intervention or not.
\item Intervention succeeds with probability $p_s$.
  \begin{itemize}
  \item If succeeds, the node is immune.
  \item If fails, the node is still susceptible.
  \end{itemize}
\item Disease transmission probability $p$.
\end{itemize}
\end{frame}

\junk{
\begin{frame}{Model}
\begin{itemize}
\item Contact graph $G=(V,E)$.
\item Each node either applies intervention or not.
\item Intervention succeeds with probability $p_s$.
  \begin{itemize}
  \item If succeeds, the node is immune.
  \item If fails, the node is still susceptible.
  \end{itemize}
\item Disease transmission probability $p$.
\end{itemize}
\end{frame}
}

\begin{frame}{Risk behavior change models}
\begin{itemize}
  \item 1-sided: disease transmission probability on $(u,v)$ is $p_m$
    if either $u$ or $v$ is intervention failed node.
  \item 2-sided: disease transmission probability on $(u,v)$ is $p_m$
    if both $u$ and $v$ are intervention failed nodes.
\end{itemize}
\begin{figure}
  \includegraphics[width=.9\textwidth]{fig/process.jpg}
\end{figure}
\end{frame}

\junk{
\begin{frame}{Process example}
\begin{columns}
  \column{0.5\textwidth}
  \begin{exampleblock}{1-sided}
    \begin{figure}
      \includegraphics[width=\textwidth]{fig/process-1sided.jpg}
    \end{figure}
  \end{exampleblock}

  \column{0.5\textwidth}
  \begin{exampleblock}{2-sided}
    \begin{figure}
      \includegraphics[width=\textwidth]{fig/process-2sided.jpg}
    \end{figure}
  \end{exampleblock}
\end{columns}
\end{frame}
}

\begin{frame}{Epidemic size calculation}
\begin{itemize}
\item Discrete time SIR (susceptible-infected-recovered) model.
\item An infected node is assume to recover in one unit of time.
\item Each infected node infects its neighbors independently with
  probability $p$ or $p_m$.
\item Epidemic size is the number of nodes that ever get infected.
\end{itemize}
\end{frame}

\begin{frame}{Less is more and non-monotonicity}
  \begin{itemize}
  \item For both 1-sided and 2-sided risk behavior models, less
    interventions may be more effective.
  \item True for both randomized and targeted strategies.
  \item Simulated on scale-free graphs and Erd\"{o}s-R\'{e}nyi random graphs.
 \end{itemize}

 \begin{figure}
   \includegraphics[width=0.5\textwidth]{fig/pa_1end_06_02_thick.jpg}
   \includegraphics[width=0.5\textwidth]{fig/pa_2end_06_02_thick.jpg}
 \end{figure}
\end{frame}

\junk{
\begin{frame}{Less is more}
\begin{columns}
  \column{0.5\textwidth}
  \begin{exampleblock}{1-sided}
    \begin{figure}
      \includegraphics[width=\textwidth]{fig/pa_1end_06_02_thick.jpg}
    \end{figure}
  \end{exampleblock}

  \column{0.5\textwidth}
  \begin{exampleblock}{2-sided}
    \begin{figure}
      \includegraphics[width=\textwidth]{fig/pa_2end_06_02_thick.jpg}
    \end{figure}
  \end{exampleblock}
\end{columns}
\end{frame}
}

\begin{frame}{Random ``may be'' better than targeted}
\begin{itemize}
\item Intervention strategies:
  \begin{itemize}
  \item Apply interventions to each node uniformly at random.
  \item Apply interventions to nodes with high degrees.
 \end{itemize}
\item In both 1-sided and 2-sided models, random intervention strategy can be better than targeted strategy.
\end{itemize}
\begin{figure}
  \includegraphics[width=0.5\textwidth]{fig/pa_cmp_1end_06_02_thick.jpg}
  \includegraphics[width=0.5\textwidth]{fig/pa_cmp_2end_06_02_thick.jpg}
\end{figure}
\end{frame}

\junk{
\begin{frame}{Random is better than targeted}
\begin{columns}
  \column{0.5\textwidth}
  \begin{exampleblock}{1-sided}
    \begin{figure}
      \includegraphics[width=\textwidth]{fig/pa_cmp_1end_06_02_thick.jpg}
    \end{figure}
  \end{exampleblock}

  \column{0.5\textwidth}
  \begin{exampleblock}{2-sided}
    \begin{figure}
      \includegraphics[width=\textwidth]{fig/pa_cmp_2end_06_02_thick.jpg}
    \end{figure}
  \end{exampleblock}
\end{columns}
\end{frame}
}

\begin{frame}{Ongoing research}
\begin{itemize}
\item Have rigorous proofs for ``less is more'' and ``random better
  than targeted'' observations.
\item Have rigorous proofs on special families of graphs
  (e.g. Erd\"{o}s-R\'{e}nyi random graphs, locally-finite infinite
  graphs).
\item Run simulations on real data sets.
\end{itemize}
\end{frame}

\subsection{Enabling positive diffusions in dynamic networks}

\begin{frame}{Resource discovery}
\begin{itemize}
\item In peer-to-peer networks, nodes can only communicate with those
  whose IP addresses are known.
\item Design efficient distributed algorithm to discover IP addresses
  on the network.
\item The network is altered \alert{dynamically} by the diffusion
  process itself.
\item Also applies to friendship discovery in social networks.
\end{itemize}
\end{frame}

\begin{frame}{Related work}
\begin{itemize}
\item \mbox{[Harchol-balter et al 1999]} studied this process with
  message size $\Omega(n)$, and showed an $O(\log^2 n)$ bound.
\item \mbox{[Law-Siu 2000]} gave an $O(\log n)$ randomized algorithm
  for resource discovery where the message size is $\Omega(n)$.
\item \mbox{[Kutten-Peleg-Vishkin 2003]} proposed a deterministic
  algorithm which solves resource discovery in $O(\log n)$ time but
  the message size is still $\Omega(n)$.
\item \mbox{[Kutten-Peleg 2002] and [Abraham-Dolev 2006]} studied
  asynchronous resource discovery.
\end{itemize}
\end{frame}

\begin{frame}{Our algorithms}
\begin{columns}
  \column{0.5\textwidth}
  \begin{itemize}
  \item Push discovery (triangulation): In each round, each node chooses
    two random neighbors and connects them by ``pushing'' their mutual
    information to each other.
  \item Notice the message size here is $O(\log n)$.
\end{itemize}

 \column{0.5\textwidth}
  \begin{exampleblock}{Triangulation process}
    \begin{figure}
      \includegraphics[width=\textwidth]{fig/model.jpg}
    \end{figure}
  \end{exampleblock}
\end{columns}
\end{frame}

\begin{frame}{Our algorithms}
\begin{columns}
  \column{0.5\textwidth}
  \begin{itemize}
  \item Pull discovery (two-hop walk): In each round, each node connects
    itself to a random neighbor of one of its randomly chosen neighbors,
    by ``pulling'' a random neighboring ID from a random neighbor.
  \item Notice the message size here is $O(\log n)$.
\end{itemize}

 \column{0.5\textwidth}
  \begin{exampleblock}{Two-hop walk process}
    \begin{figure}
      \includegraphics[width=\textwidth]{fig/model2.jpg}
    \end{figure}
  \end{exampleblock}
\end{columns}
\end{frame}

\begin{frame}{Ongoing research}
\begin{itemize}
\item We are interested in the converging time.
\item In undirected graphs, we showed the upper bound for both
  triangulation process and two-hop walk process is $O(n\log^2 n)$,
  while $\Omega(n\log n)$ is the lower bound.
\item In directed graphs, we showed the upper bound for two-hop walk
  process is $O(n^2\log n)$, while the lower bound is $\Omega(n^2\log n)$
  for weakly connected graphs and $\Omega(n^2)$ for strongly connected
  graphs.
\item We conjecture that both processes complete in $O(n\log n)$ time
  in undirected graphs.
\end{itemize}
\end{frame}

\begin{frame}{Information dissemination in adversarial networks}
\begin{itemize}
\item $k$ different pieces of information assigned to a set of nodes.
\item Goal is to diffuse all $k$ pieces of information to every node
  on the network.
\item We consider \alert{adversarial network}.
\end{itemize}
\end{frame}

\begin{frame}{Related work}
\begin{itemize}
\item \mbox{[Kuhn et al 2010]} studied information dissemination
  problem in adversarial networks, and showed a tight bound $O(kn)$
  in the ``shout-out'' model with message size $O(\log n)$.
\item \mbox{[Haeupler-Karger 2011]} studied the same problem using network
  encoding.
\item \mbox{[Karp-Schindelhauer-Shenker-V\"{o}cking 2000]} introduced
  pull and push models.
\item \mbox{[Boyd-Ghosh-Prabhakar-Shah 2006]} studied randomized
  gossip algorithms.
\item \mbox{[Mosk-Aoyama-Shah 2006]} studied how to compute separable
    functions via gossip.
\end{itemize}
\end{frame}

\begin{frame}{Proposed research}
\begin{itemize}
\item Design efficient algorithms for information dissemination problems in
  other models.
\item Randomized vs deterministic.
\item Centralized vs distributed.
\item Broadcast vs unicast.
\item Resilience of the communication links.
\item Power of the adversary.
\item {\em RandomizedTokenForwarding:} In each round, node $u$ sends
  a piece of information to each of its neighbors which they don't
  have yet.
\end{itemize}
\end{frame}

\appendix
\section<presentation>*{Conclusion}
\begin{frame}{Conclusion}
\begin{itemize}
\item Controlling harmful diffusions.
  \begin{itemize}
  \item Give a $2d$ (or $O(\log n)$) approximation algorithm for
    centralized intervention strategies.
  \item Show the existence (or non-existence) for decentralized
    intervention strategies, and give performance bound on the
    decentralized solutions with respect to optimal centralized
    solutions. 
  \item With the existence of risk behaviors, observe interesting
    phenomena and propose to give rigorous proofs.
  \end{itemize}
\item Enabling positive diffusions in dynamic networks.
  \begin{itemize}
  \item Resource discovery: give almost tight bounds on converging
    time for both triangulation and two-hop walk processes.
  \item Information dissemination in adversarial network: propose to
    devise efficient algorithms.
  \end{itemize}
\end{itemize}
\end{frame}

\end{document}

